package top.hkyzf.study.leetcode.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * description: 
 * @author zhufeng
 * @date 2024/4/7 0007 10:21
 * @version V1.0
 */
public class ThroneInheritance {
    public Map<String, List<String>> peopleMap = new HashMap<>();
    public Set<String> dead = new HashSet<>();
    public String kingName;

    public ThroneInheritance(String kingName) {
        List<String> kingList = new ArrayList<>();
        kingList.add(kingName);
        peopleMap.put(kingName, kingList);
        this.kingName = kingName;
    }

    public void birth(String parentName, String childName) {
        List<String> parentList = peopleMap.get(parentName);
        if (parentList == null) {
            parentList = new ArrayList<>();
            parentList.add(parentName);
            parentList.add(childName);
        } else {
            parentList.add(childName);
        }
        peopleMap.put(parentName, parentList);
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        List<String> kingList = peopleMap.get(kingName);
        if (kingList == null) {
            if (!dead.contains(kingName)) {
                order.add(kingName);
            }
        } else {
            getChild(kingList, order);
        }
        return order;
    }

    public void getChild(List<String> list, List<String> result) {
        if (!dead.contains(list.get(0))) {
            result.add(list.get(0));
        }
        for (int i = 1; i < list.size(); i++) {
            String child = list.get(i);
            if (child != null) {
                List<String> childList = peopleMap.get(child);
                if (childList == null) {
                    if (!dead.contains(child)) {
                        result.add(child);
                    }
                } else {
                    getChild(childList, result);
                }
            }
        }
    }
}
